package com.dyz.leetcode._09_heapAndPriorityQueue;

import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class _239_maxSlidingWindow {
    //暴力解法
    public int[] maxSlidingWindow1(int[] nums, int k) {
        int n = nums.length;
        int[] ans = new int[n-k+1];

        for (int i = 0; i <n-k+1 ; i++) {
            int max = Integer.MIN_VALUE;
            for (int j = i; j < i+k; j++) {
                 max = Math.max(max, nums[j]);

            }
            ans[i] = max;
        }
        return ans;
    }
    //大顶堆
    public int[] maxSlidingWindow(int[] nums, int k) {
        PriorityQueue<int[]> pq
                = new PriorityQueue<>((a, b) -> a[0] != b[0] ? b[0] - a[0] : b[1] - a[1]);
        for (int i = 0; i < k; i++) {
            pq.add(new int[]{nums[i], i});
        }

        int[] ans = new int[nums.length - k + 1];
        ans[0] = pq.peek()[0];
        for (int i = k; i < nums.length; i++) {
            pq.add(new int[]{nums[i], i});
            while (pq.peek()[1] <= i - k) {
                pq.remove();
            }
            ans[i - k + 1] = pq.peek()[0];
        }

        return ans;
    }

    //双端队列
    public int[] maxSlidingWindow2(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<>();
        int[] ans = new int[n - k + 1];

        for(int i = 0; i<nums.length;i++){
            // 保证队列里面最多只有 k 个元素
            // 说明：这里的 while 可以使用 if 来代替，因为：
            // 要维护一个大小为 k 的窗口的话，每次最多只需要处理一个元素即可
            while(!deque.isEmpty() && deque.peek()<=i-k){
                deque.poll();
            }
            // 保证队列里面最多只有 k 个元素
            // 说明：这里的 while 可以使用 if 来代替，因为：
            // 要维护一个大小为 k 的窗口的话，每次最多只需要处理一个元素即可
            while (!deque.isEmpty() && nums[i]>nums[deque.peekLast()]){
                deque.pollLast();
            }
            //插入队尾
            deque.offer(i);
            if (i >= k - 1) {ans[i - k + 1] = nums[deque.peek()];}
        }

        return ans;
    }
}
